package com.example.leetcode.prcatice;

/**
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 *
 * <p>子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。 示例 2：
 *
 * <p>输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test516 {

    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];      // 动态规划dp[i][j]表示下标i到j的最长序列长度
        // 转移方程
        for (int i = len-1;i>=0;i--){
            dp[i][i] = 1;
            char c = s.charAt(i);
            for (int j = i+1;j<len;j++){
                int c1 = s.charAt(j);
                if(c1 == c){
                    dp[i][j] = dp[i+1][j-1] +2;   // 小标i和j的位置相等，长度加2
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}



class Demo516{
  public static void main(String[] args) {
    Test516 t = new Test516();
    String s = "bbbab";
    System.out.println(t.longestPalindromeSubseq(s));
  }
}